这道题是一道典型的搜索题,我们用表示蜗牛在这个点,走了步,当前的方向(起点的,特殊处理一下)。
当蜗牛确定一个方向后,我们就不断让它前进,同时记录它走过的格子,直到它遇到障碍,出界或者到达已走过的点停止。
如果蜗牛遇到障碍,我们就枚举每个方向,因为前方有障碍,后方已经走过,所以蜗牛只会向左或向右转,不需要特殊处理。
Chihik's Blog
这道题是一道典型的搜索题,我们用dfs(x,y,step,s)表示蜗牛在(x,y)这个点,走了step步,当前的方向(起点的s=0,特殊处理一下)。
当蜗牛确定一个方向后,我们就不断让它前进,同时记录它走过的格子,直到它遇到障碍,出界或者到达已走过的点停止。
如果蜗牛遇到障碍,我们就枚举每个方向,因为前方有障碍,后方已经走过,所以蜗牛只会向左或向右转,不需要特殊处理。
这道题明显是线段树的板题,至于考试时因为懒标记的小问题只有20分,我也很无奈。
进入正题,既然要修改查询区间内连续的一段元素,似曾相识的感觉。
我们等价的把空房子看为1,住人的房子看为0。
为了书写方便,我们将′L′表示为0,′R′表示为1。
现在题目转化为给你一个01矩阵,每次可将一行或一列的01反转,要求最后只有一个1或只有一个0,问能否办到。
现在,我们将第一行和第一列的元素全变为1(0也可以),这个很好办到,翻转第一行的元素就将该元素所在列翻转,列同理。
这道题边的数量最高是10000多,而点只有500,这提醒我们,我们不能直接对边求期望,而是点。
设Expection[u]表示点u的期望走过次数,Degree[u]表示点u的度数。
那么,
如果没有不能走到的点,这道题就非常简单了。我们只需向下走h−1步,向右走w−1步,就可到达右下角。在这h+w−2步中,我们选h−1向下走,那么答案为Ch+w−2h−1。
但是,棋盘中有些点是不能走的,我们考虑用容斥原理去除多余方案,即
首先,我们将所有源点与汇点筛出来,然后从每一个源点dfs求出它到各汇点的路径数,题目中保证源点与汇点数量相同,我们记为cnt。
那么,我们可以得到一个cnt∗cnt的矩阵。
先考虑路径不相交的情况(似乎大家思路都是这样),题目求的是一个排列的逆序对数,记为τ(σ)。那么,题目等价于求: